﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphTheory.Task1
{
    class Digraph
    {
        public int[] Vertices { get; private set; }
        public int[,] AdjacencyMatrix { get; private set; }

        public Digraph(int[] Vertices, int[,] AdjacencyMatrix)
        {
            this.Vertices = Vertices;
            this.AdjacencyMatrix = AdjacencyMatrix;
        }

        public Digraph(int VerticesAmount, int[,] AdjacencyMatrix)
        {
            this.Vertices = new int[VerticesAmount];
            for (int i = 0; i < VerticesAmount; i++)
            {
                this.Vertices[i] = i;
            }
            this.AdjacencyMatrix = AdjacencyMatrix;
        }

        public static Digraph ParseFromString(string str)
        {
            StringScanner scanner = new StringScanner(str);
            int VerticesAmount = scanner.nextInt();
            int[,] AdjacencyMatrix = new int[VerticesAmount, VerticesAmount];
            int[,] WeightMatrix = new int[VerticesAmount, VerticesAmount];

            for (int i = 0; i < VerticesAmount; i++)
            {
                for (int j = 0; j < VerticesAmount; j++)
                {
                    AdjacencyMatrix[i, j] = scanner.nextInt();
                }
            }

            return new Digraph(VerticesAmount, AdjacencyMatrix);
        }

        public List<int>[] GetStronglyConnectedComponents()
        {
            int n = 0;
            List<int> F = new List<int>();
            Stack<int> S = new Stack<int>();
            int[] M = new int[this.Vertices.Length];
            int[] L = new int[this.Vertices.Length];
            List<List<int>> Components = new List<List<int>>();
            find(this.Vertices.First(), F, S, ref n, M, L, Components);
            Components.Reverse();
            return Components.ToArray();
        }

        private void find(int vertex, List<int> F, Stack<int> S, ref int n, int[] M, int[] L, List<List<int>> Components)
        {
            F.Add(vertex);
            int index = GetIndex(this.Vertices, vertex);
            M[index] = n;
            n++;
            L[index] = M[index];
            S.Push(vertex);
            List<int> outgoing = GetOutgoingVertices(this, vertex);
            foreach (var vrt in outgoing)
            {
                if (!F.Contains(vrt))
                {
                    find(vrt, F, S, ref n, M, L, Components);
                    L[index] = Math.Min(L[index], L[GetIndex(this.Vertices, vrt)]);
                }
                else if (//M[GetIndex(this.Vertices, vrt)] < M[index] && 
                    S.Contains(vrt))
                {
                    L[index] = Math.Min(L[index], M[GetIndex(this.Vertices, vrt)]);
                }
            }

            if (L[index] == M[index])
            {
                
                List<int> newComponent = new List<int>();
                int vrt = -1;
                do
                {
                    vrt = S.Pop();
                    newComponent.Add(vrt);
                } while (vrt != vertex);
                newComponent.Reverse();
                Components.Add(newComponent);
            }
        }

        private static int GetIndex(int[] Vertices, int vrt)
        {
            for (int i = 0; i < Vertices.Length; i++)
            {
                if (Vertices[i] == vrt)
                {
                    return i;
                }
            }
            throw new ArgumentException();
        }

        public static List<int> GetOutgoingVertices(Digraph digraph, int vertex)
        {
            int index = GetIndex(digraph.Vertices, vertex);
            List<int> res = new List<int>();
            for (int j = 0; j < digraph.Vertices.Length; j++)
            {
                if (digraph.AdjacencyMatrix[index, j] == 1)
                {
                    res.Add(digraph.Vertices[j]);
                }
            }

            return res;
        }

        public void AddArc(int source, int sink)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            this.AdjacencyMatrix[indexSource, indexSink] = 1;
        }

        public void DeleteArc(int source, int sink)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            this.AdjacencyMatrix[indexSource, indexSink] = 0;
        }

        private Tuple<int, int> firstArcFrom(int vertex)
        {
            int index = GetIndex(this.Vertices, vertex);
            for(int j = 0; j < this.Vertices.Length; j++)
            {
                if (this.AdjacencyMatrix[index, j] == 1)
                {
                    return new Tuple<int, int>(vertex, this.Vertices[j]);
                }
            }
            return null;
        }

        private Tuple<int, int> nextArcFrom(Tuple<int, int> arc)
        {
            int indexBeg = GetIndex(this.Vertices, arc.Item1);
            int indexEnd = GetIndex(this.Vertices, arc.Item2);
            for (int j = indexEnd + 1; j < this.Vertices.Length; j++)
            {
                if (this.AdjacencyMatrix[indexBeg, j] == 1)
                {
                    return new Tuple<int, int>(arc.Item1, this.Vertices[j]);
                }
            }
            return null;
        }

    }
}
